//
// Created by bleedingfight on 2020/6/29.
//
#include "fastsort.h"
// 6 5 4 7 3 1 9
// 6 5 4 1 3 7 9
// 3 5 4 1 6 7 9
void fastsort(std::vector<int>&nums,int left,int right){
    int prviot = nums[left];
    int i = left;
    int j = right;
    if(left>=right)//刚刚漏了这里，否则递归没有结束条件了
        return;
    while(i!=j){
        while(i<j&&nums[j]>=prviot)
            j--;
        while (i<j&&nums[i]<=prviot)
            i++;
        // 下标操作后没法保证i<j,加上这个表示在i<j的时候才交换
        if(i<j)
            std::swap(nums[i],nums[j]);
    }
    nums[left] = nums[j];
    nums[i] = prviot;
    fastsort(nums,left,i-1);
    fastsort(nums,i+1,right);
}
